#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct Edge
{
    int u, v;
};

bool d[ 16 ][ 16 ], visit[ 16 ], visit2[ 16 ], hash[ 3110903 ];
int n, cnt, hk[] = { 101, 233, 335, 337, 541, 571, 631, 751, 823, 971, 1033, 1039, 1061, 1123, 1151 };
Edge e[ 16 ];

void init( )
{
    int i;
    memset( d, 0, sizeof( d ) );
    scanf("%d", &n);
    for ( i = 0; i < n - 1; i++ )
    {
        scanf("%d%d", &e[ i ].u, &e[ i ].v); e[ i ].u--; e[ i ].v--;
        d[ e[ i ].u ][ e[ i ].v ] = d[ e[ i ].v ][ e[ i ].u ] = true;
    }
    memset( hash, 0, sizeof( hash ) );
    cnt = 0;
}

int dfs2( int p )
{
    int i, a[ 16 ], m = 0, ret = 0;
    visit[ p ] = visit2[ p ] = true;
    for ( i = 0; i < n; i++ )
    {
        if ( visit[ i ] )
            continue;
        if ( d[ p ][ i ] )
            a[ m++ ] = dfs2( i );
    }
    if ( !m )
        return 1234;
    sort( a, a + m );
    ret = ( a[ 0 ] * hk[ m ] ) % 310193;
    for ( i = 1; i < m; i++ )
        ret = ( ( ret ^ a[ i ] ) * hk[ m ] ) % 310193;
    return ret;
}

void dfs( int p )
{
    int i, j, h, t;
    memset( visit, 0, sizeof( visit ) );
    memset( visit2, 0, sizeof( visit2 ) );
    for ( i = 0; i < n; i++ )
    {
        if ( !visit2[ i ] )
        {
            memset( visit, 0, sizeof( visit ) );
            h = dfs2( i );
            if ( !hash[ h ] )
            {
                t = 0;
                hash[ h ] = true;
                for ( j = 0; j < n; j++ )
                    if ( visit[ j ] )
                    {
                        memset( visit, 0, sizeof( visit ) );
                        h = dfs2( j );
                        hash[ h ] = true;
                    }
//                printf("%d %d\n",t, h);
                cnt++;
            }
        }
    }
    for ( i = p; i < n - 1; i++ )
    {
        d[ e[ i ].u ][ e[ i ].v ] = d[ e[ i ].v ][ e[ i ].u ] = false;
        dfs( i + 1 );
        d[ e[ i ].u ][ e[ i ].v ] = d[ e[ i ].v ][ e[ i ].u ] = true;
    }
}

int main( )
{
    int t, cas = 1;
    scanf("%d", &t);
    while ( t-- )
    {
        init( );
        dfs( 0 );
        printf("Case #%d: %d\n", cas++, cnt);
    }
    return 0;
}
